/**
 * @file DP01.java
 * @brief 文件简要说明
 * <p>
 * 文件详细说明
 * @author - 2024/10/18  贾思浩  创建初始版本
 * @version - 2024/10/18  V1.0  简要版本说明
 * @par 版权信息：
 * 2024 Copyright 北京鑫万佳科技发展科技有限公司 All Rights Reserved.
 */
package com.dp;

/**
 *
 * @brief 类简要说明
 *
 * 类详细说明    线性dp
 *
 *@author
 *    - 2024/10/18  贾思浩  创建初始版本
 *
 */
public class DP01 {
     /*   给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
        子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
                子序列。*/
    // 最长递增子序列
    public int lc300(int[] nums) {
        int n = nums.length;
        int dp[] = new int[n];
        int res = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }

    // lc32 最长有效括号
    /** 假设dp[i] 为以s[i]结尾的最长有效括号长度，
     *  当 s[i] = ( ,dp[i] = 0
     *  当 s[i] = ) ,s[i-1] = ( ,dp[i] = dp[i-2] + 2;
     *  当 s[i] = ) ,s[i-1] = ) , s[i - dp[i-1] -1] = ( , dp[i] = dp[i-1]  + 2 + dp[i - dp[i-1] -1];
     *  当 s[i] = ) ,s[i-1] = ) , s[i - dp[i-1] -1] = ) , dp[i] = 0;
     *
     *
     * */
    public int lc32(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        int res = 0;
        int[] dp = new int[length];
        for (int i = 1; i < length; i++) {
            if (chars[i] == '(')
                dp[i] = 0;
            else {
                if (chars[i - 1] == '(')
                    dp[i] = 2 + (i-2 >= 0 ? dp[i-2] : 0);
                else {
                    if (i - dp[i-1] -1< 0 || chars[i -dp[i-1] -1] == ')') {
                        dp[i]= 0;
                    } else {
                        dp[i] = dp[i-1] + 2 + (i - dp[i-1]  - 2 >=0 ?dp[i - dp[i-1]  - 2] : 0 );
                    }
                }
            }

            res = Math.max(res, dp[i]);
        }
        return res;
    }
    // lc1143 最长公共子序列
    /*
    * 定义dp[i][j] 为 text1(0,i) 与 text2(0,j) 的最长公共子序列
    * text1[i] == text2[j]  dp[i][j] = dp[i-1][j-1] + 1;
    * text1[i] != text2[j]  dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
    *
    * */
    public int lc1143 (String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char c2 = text2.charAt(j -1);
                if (c1 == c2) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
    }

    // lc97 交错字符串
    public boolean lc97(String s1, String s2, String s3) {


        return true;
    }
}
